package 贪心算法.最大子数组和;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/3/25 20:45
 * @description:请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 动态规划 f(i)=max{f(i−1)+nums[i],nums[i]}
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }

    public static int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            //pre用来筛选当前数字是否能够加入自己，变得更大
            //如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加
            pre = Math.max(pre + x, x);
            //maxAns用来筛选出最大的连续子数组的和
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

}
